package com.captain.special.二叉树.中等;

import com.captain.leetcode.TreeNode;

import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.List;

/**
 * Des:
 *
 * @author XL
 * @Date 2022/5/18 17:16
 */
public class 路径总和II113 {
    List<List<Integer>> ans;
    int target;
    Deque<Integer> path = new LinkedList<>();

    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        ans = new ArrayList<>();
        target = targetSum;
        recur(root, 0);
        return ans;
    }

    public void recur(TreeNode node, int sum) {
        if (node == null) {
            return;
        }
        path.offerLast(node.val);
        sum = sum + node.val;
        if (sum == target && node.left == null && node.right == null) {
            ans.add(new ArrayList<>(path));
        }
        recur(node.left, sum);
        recur(node.right, sum);
        path.removeLast();
    }
}
